9635. Transport system
The transport system of Baku
consists of n intersections and m two-way roads connecting these
intersections. Each road connects exactly two intersections, and no pair of
intersections can be connected by more than one road. Moving along these roads,
you can go from any intersection to any other. The distance between two
intersections is the minimum number of roads among all paths connecting these
intersections.
To improve the transport
system, the city mayor demanded that the director of the transport system must
build a new road. However, mayor bought a new car and every day enjoys a trip
from home to work and from work home. He does not want the distance between the
intersection s where his house is
located and the intersection t where
his work is located to be reduced. Help the director of the transport system to
solve this problem, an to fulfill the requirement of the mayor.
Your task is to find the
number of pairs of unconnected intersections that, having travelled between
them, the distance between the intersections s and t will not
decrease.
Input.
First line contains four integers: number of intersections n (1 ≤ n ≤ 103),
number of roads m (1 ≤ m ≤ 105), intersection s with home, intersection t with work (1 ≤ s, t
≤ n, s ≠ t). Then m lines are given, i-th line contains two integers ui
and vi (1 ≤ ui, vi ≤ n, ui ≠ vi). They mean that there is
a two-way road between intersections ui and vi.
Output. Print the number of required intersection pairs.
|
Sample input 1 |
Sample output 1 |
|
5 4 1 5 1 2 2 3 3 4 4 5 |
0 |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
5 4 3 5 1 2 2 3 3 4 4 5 |
5 |
SOLUTION
graphs, breadth
first search
Algorithm analysis
Start a breadth first search
from the starting s and
final f vertices.
Accordingly, the shortest distances from s will be
stored in
array distS, the shortest distances
from f will be stored in array distF.
Let optDistance be the shortest distance
between s and f in original graph.
Consider is it possible to construct a new road
between the vertices
i and j.
After road construction between i and j, new paths s → i → j → f of
length distS[i] + 1 + distF[j] and s → j → i → f of
length distS[j] + 1 + distF[i] are formed. If at least one of these distances is less
than optDistance, then construction of the road (i, j) will reduce the
shortest distance between s and f, and in this case it does not suit us.
It remains to
iterate over all possible pairs i and
j and check whether the new road (i, j) will reduce the
shortest distance between s and f.
Example
Graph
from the first test case is shown on the left. The shortest distance from 1
to 5 is 4. Whichever new road we take, the distance between 1 and 5 will be
reduced. Therefore, no required road exists.
Graph
from the second test case is shown on the right. The shortest distance from
3 to 5 is 2. The bold lines show possible roads. Whichever one of these roads
is built, the distance between 3 and 5 will not decrease.
Algorithm realization
Declare a constant MAX – the maximum possible number
of graph vertices.
#define MAX 1001
Declare an adjacency matrix g.
int g[MAX][MAX], distS[MAX], distF[MAX];
Function bfs implements the breadth first search from vertex
start. It is passed an array of
shortest distances dist.
void bfs(int start, int *dist)
{
Initialize the array of shortest distances dist.
for (int i = 0; i <=
n; i++) dist[i] = -1;
dist[start] = 0;
Declare a queue. Push the starting vertex into it.
queue<int> q;
q.push(start);
While the queue is not empty, pop the
vertex v from it.
while (!q.empty())
{
int v = q.front(); q.pop();
Iiterate over the vertices to adjacent to v. If the vertex to
has not yet been visited, compute the shortest distance dist[to] to it and push it into the queue.
for (int to = 1; to <= n; to++)
if (g[v][to] && dist[to] == -1)
{
q.push(to);
dist[to] = dist[v] + 1;
}
}
}
The main part of the program. Read the
input data.
scanf("%d %d %d %d", &n, &m, &s, &f);
memset(g, 0, sizeof(g));
Read an undirected graph.
for (i = 0; i < m; i++)
{
scanf("%d
%d", &a, &b);
g[a][b] = g[b][a] = 1;
}
Run the breadth -first
search from vertices s and f. Store the
shortest distances into arrays distS
and distF, respectively.
bfs(s, distS);
bfs(f, distF);
The shortest
distance between
s and f in the original graph is optDistance.
optDistance = distS[f];
Iterate through
the pairs of vertices i and j and try to construct a new road
between them. In the variable res count
the number of possible new roads.
res = 0;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
If there is no road between i and j yet, then compute the lengths of
the shortest paths s → i → j → f and s → j → i → f. If
they are not less than optDistance,
then such road can be built.
if (g[i][j] == 0)
{
if ((distS[i] +
distF[j] + 1 >= optDistance) &&
(distS[j] +
distF[i] + 1 >= optDistance))
res++;
}
Print the answer.
printf("%d\n", res);
Java realization
import java.util.*;
public class Main
{
static int g[][], distS[], distF[];
static int n, m, s, f;
static void bfs(int start, int dist[])
{
Arrays.fill(dist,-1);
dist[start] = 0;
Queue<Integer> q = new
LinkedList<Integer>();
q.add(start);
while(!q.isEmpty())
{
int v = q.poll();
for (int to = 1; to <= n; to++)
if (g[v][to] == 1
&& dist[to] == -1)
{
q.add(to);
dist[to] = dist[v] + 1;
}
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
n = con.nextInt();
m = con.nextInt();
s = con.nextInt();
f = con.nextInt();
g = new int[n+1][n+1];
distS = new int[n+1];
distF = new int[n+1];
for (int i = 1; i <= m; i++)
{
int a = con.nextInt();
int b = con.nextInt();
g[a][b] = g[b][a] = 1;
}
bfs(s, distS);
bfs(f, distF);
int optDistance = distS[f];
int res = 0;
for(int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (g[i][j] == 0)
{
if ((distS[i] + distF[j] + 1 >= optDistance) &&
(distS[j] + distF[i] + 1 >= optDistance))
res++;
}
System.out.println(res);
con.close();
}
}